Codility Lesson 12 - ChocolatesByNumbers

문제 설명

두 개의 양의 정수 N과 M이 주어집니다. 정수 N은 0에서 N-1까지 번호가 매겨진 원 안에 배열된 초콜릿의 개수를 나타냅니다.

당신은 초콜릿을 먹기 시작합니다. 초콜릿을 먹은 후 포장지만 남깁니다.

0번 초콜릿부터 먹기 시작합니다. 그런 다음 원 안에 있는 다음 M-1개의 초콜릿 또는 포장지를 생략하고 다음 초콜릿을 먹습니다.

더 정확하게 말하면, 초콜릿 번호 X를 먹었다면 다음에는 숫자 (X + M) 모듈로 N(나머지 나눗셈)이 있는 초콜릿을 먹습니다.

빈 포장지를 발견하면 먹기를 중단합니다.

예를 들어, 정수 N = 10과 M = 4가 주어집니다. 다음 초콜릿을 먹습니다: 0, 4, 8, 2, 6.

목표는 위의 규칙에 따라 먹을 초콜릿의 개수를 세는 것입니다.

함수를 작성합니다:

function solution(N, M);

두 개의 양의 정수 N과 M이 주어지면 먹을 초콜릿의 개수를 반환하는 함수를 작성합니다.

예를 들어 정수 N = 10, M = 4가 주어지면 위에서 설명한 대로 함수는 5를 반환해야 합니다.

다음 가정에 대한 효율적인 알고리즘을 작성하십시오:

• N과 M은 [1..1,000,000,000] 범위 내의 정수입니다.

문제 접근

규칙은 최대공약수의 배수이다.

유클리드 호제법을 이용하여 최대공약수를 구할수이다.

// 단, a가 b보다 커야함.
function gcd(a, b) { 
  let r;
  
  while ((a % b) > 0)  {
    r = a % b;
    a = b;
    b = R;
  }
  
  return b;
}

1. 유클리드 호제법을 이용하여 최대공약수를 구한다.
2. N을 최대공약수로 나누게 되면 갯수가 나온다.

function solution(N, M) {
    let a = N;
    let b = M;
    let remain = 0;

    while (a % b !== 0) {
        remain = a % b;
        a = b;
        b = remain;
    }

    return Math.floor(N / b);
}